package com.fyl.basic_algorithm.sorts;


import java.util.Collections;

import static java.util.Collections.swap;

/**
 * @author 冯永龙
 * @date 2021/4/2 15:39
 */
public class Heap {
    private int[] a; //数组，从下标为1开始储存数据
    private int n; //堆中可以储存的最大数据个数
    private int count; //堆中已经储存的数据个数

    public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    //插入
    public void insert(int data) {
        if (count >= n) return; //堆满了

        ++count;
        a[count] = data;
        int i = count;
        while (i / 2 > 0 && a[i] > a[i / 2]) {
            swap(Collections.singletonList(a), i, i / 2);
            i = i / 2;
        }
    }

    //移除最大节点
    public void removeMax() {
        if (count == 0) return; //堆中没有元素

        //将最后一个节点放到堆顶
        a[1] = a[count];
        --count;
        heapify(a, count, 1);
    }

    //建堆
    public void buildHeap(int[] a, int n) {
        //a[n/2]为最后一个叶子节点的父节点，也就是最后一个非叶子节点，依次堆化直到根节点
        for (int i = n / 2; i >= 1; i--) {
            heapify(a, n, i);
        }
    }

    //排序
    public void sort(int[] a, int n) {
        if (count<=1) return;
        //建堆
        buildHeap(a, n);

        int k = n;
        while (k > 1) {
            //将堆顶元素（最大）与最后一个元素交换位置
            swap(Collections.singletonList(a), 1, k);
            //将剩下元素重新堆化，堆顶元素变成最大元素
            k--;
            heapify(a,k,1);
        }
    }

    /**
     * 堆化
     *
     * @param a 要堆化的数组
     * @param n 最后堆元素的下标
     * @param i 要堆化元素的下标
     */
    private void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            //与左子节点a[i*2]比较，获取最大值位置
            if (i * 2 <= n && a[i] < a[i * 2]) {
                maxPos = i * 2;
            }
            //与右子节点a【i*2+1】比较，获取最大值
            if (i * 2 + 1 <= n && a[i] < a[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            //最大值是当前位置结束循环
            if (maxPos == i) {
                break;
            }
            //与子节点交换位置
            swap(Collections.singletonList(a), i, maxPos);
            //以交换后子节点位置接着往下查找
            i = maxPos;
        }
    }

}
